﻿#region Copyright Notice
// 
// 
//  
//  Copyright (c) 2009-2011 Anindya Chatterjee
//  
//  Licensed under the Apache License, Version 2.0 (the "License");
//  you may not use this file except in compliance with the License.
//  You may obtain a copy of the License at
//  
//      http://www.apache.org/licenses/LICENSE-2.0
//  
//  Unless required by applicable law or agreed to in writing, software
//  distributed under the License is distributed on an "AS IS" BASIS,
//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//  See the License for the specific language governing permissions and
//  limitations under the License.
// 
// 
#endregion
using System;
using System.Collections.Generic;
using System.Linq;
using AbstractClass.Collections.Generic;
using NUnit.Framework;

namespace QuasarTest.Core
{
    [TestFixture]
    public class BinaryTreeTest
    {
        #region Setup/Teardown

        [SetUp]
        public void Init()
        {
            _tree = new BinaryTree<int>();
        }

        #endregion

        private BinaryTree<int> _tree;

        [Test]
        public void TestAddNode()
        {
            var nodeA = new BinaryTreeNode<int> {Value = 2};
            Assert.IsTrue(_tree.AddNode(nodeA));

            var nodeB = new BinaryTreeNode<int>(3);
            Assert.IsTrue(_tree.AddNode(nodeB));

            var nodeC = new BinaryTreeNode<int>(4);
            Assert.IsTrue(_tree.AddNode(nodeC));

            Assert.AreEqual(nodeC.Parent, nodeA);
            Assert.IsTrue(nodeC.IsSibling(nodeB));

            foreach (int element in Enumerable.Range(5, 100))
            {
                _tree.AddNode(element);
            }

            Assert.AreEqual(_tree.Count, 103);
        }

        [Test]
        public void TestBinaryTreeProperties()
        {
            foreach (int element in Enumerable.Range(0, 15))
            {
                _tree.AddNode(element);
            }

            //The number of nodes n in a perfect binary tree can be found using this formula: n = 2^(h + 1) − 1 where h is the height of the tree
            int height = _tree.Height;
            double nodeCount = Math.Pow(2, (height + 1)) - 1;
            Assert.IsTrue(_tree.IsPerfectBinaryTree);
            Assert.AreEqual(nodeCount, _tree.Count);

            //The number of nodes n in a perfect binary tree can also be found using this formula: n = 2L − 1 where L is the number of leaf nodes in the tree
            Assert.AreEqual(_tree.Count, 2 * _tree.Leaves.Count() - 1);

            //The number of leaf nodes n in a perfect binary tree can be found using this formula: n = 2^h where h is the height of the tree
            double leafCount = Math.Pow(2, _tree.Height);
            Assert.AreEqual(_tree.Leaves.Count(), leafCount);

            //For any non-empty binary tree with n0 leaf nodes and n2 nodes of degree 2, n0 = n2 + 1
            int degreeTwoNodeCount = _tree.ToEnumerable.Where(x => x.ChildCount == 2).Count();
            Assert.AreEqual(leafCount, degreeTwoNodeCount + 1);

            //n = n0 + n1 + n2 + n4 + n3 + n5 + .... + nB-1 + nB 
            int n = _tree.Count;
            int n0 = _tree.Leaves.Count();
            int n1 = _tree.ToEnumerable.Where(x => x.ChildCount == 1).Count();
            int n2 = degreeTwoNodeCount;
            Assert.AreEqual(n, n0 + n1 + n2);

            //B = 1*n1 + 2*n2 + 3*n3 + 4*n4 + ... + B*nB, NOT include n0, B = the branches in Tree
            int branchCount = n - 1;
            Assert.AreEqual(branchCount, 1 * n1 + 2 * n2);
        }

        [Test]
        public void TestClear()
        {
            _tree.Clear();
            Assert.AreEqual(_tree.Count, 0);
        }

        [Test]
        public void TestDelete()
        {
            foreach (int element in Enumerable.Range(0, 100))
            {
                _tree.AddNode(element);
            }

            Assert.AreEqual(_tree.Count, 100);
            Assert.IsTrue(_tree.DeleteNode(98));
            Assert.IsFalse(_tree.HasNode(98));
            Assert.AreEqual(_tree.Count, 99);

            BinaryTreeNode<int> node = _tree.TryGetNode(97);
            Assert.IsTrue(_tree.DeleteNode(node));
            Assert.IsFalse(_tree.HasNode(97));

            Assert.AreEqual(_tree.Root.Value, 0);
            Assert.IsTrue(_tree.DeleteNode(0));
            Assert.AreEqual(_tree.Root.Value, 94);
            Assert.IsNull(_tree.Root.Parent);
        }

        [Test]
        public void TestFind()
        {
            foreach (int element in Enumerable.Range(0, 10))
            {
                _tree.AddNode(element);
            }

            Assert.NotNull(_tree.TryGetNode(5));
            Assert.IsTrue(_tree.HasNode(7));
            Assert.IsFalse(_tree.HasNode(11));
            Assert.IsNull(_tree.TryGetNode(13));
        }

        [Test]
        public void TestGetSubtree()
        {
            foreach (int element in Enumerable.Range(0, 15))
            {
                _tree.AddNode(element);
            }

            BinaryTreeNode<int> newRoot = _tree.TryGetNode(2);
            var tree = (BinaryTree<int>) _tree.GetSubtree(newRoot).Clone();
            Assert.AreEqual(tree.Count, 7);

            Assert.IsTrue(tree.IsFullBinaryTree);
            Assert.IsFalse(tree.IsDegeneratedBinaryTree);
            Assert.IsTrue(tree.IsBalancedBinaryTree);
            Assert.IsTrue(tree.IsPerfectBinaryTree);

            Assert.IsTrue(tree.AddNode(20));
            Assert.IsTrue(tree.HasNode(20));
            Assert.IsFalse(_tree.HasNode(20));
            Assert.AreEqual(tree.Count, 8);

            Assert.IsFalse(tree.IsFullBinaryTree);
            Assert.IsFalse(tree.IsDegeneratedBinaryTree);
            Assert.IsTrue(tree.IsBalancedBinaryTree);
            Assert.IsFalse(tree.IsPerfectBinaryTree);
            Assert.IsTrue(tree.HasNode(13));
            Assert.NotNull(tree.Root.Parent);
        }

        [Test]
        public void TestLeaves()
        {
            foreach (int element in Enumerable.Range(0, 15))
            {
                _tree.AddNode(element);
            }

            Assert.IsTrue(_tree.Leaves.All(x => x.ChildCount == 0));
        }

        [Test]
        public void TestTraverse()
        {
            foreach (int element in Enumerable.Range(0, 15))
            {
                _tree.AddNode(element);
            }

            var inOrderList = new List<BinaryTreeNode<int>>();
            var postOrderList = new List<BinaryTreeNode<int>>();
            var preOrderList = new List<BinaryTreeNode<int>>();

            _tree.Traverse(inOrderList.Add, BinaryTreeTraversalOrder.InOrder);
            _tree.Traverse(postOrderList.Add, BinaryTreeTraversalOrder.PostOrder);
            _tree.Traverse(preOrderList.Add, BinaryTreeTraversalOrder.PreOrder);

            Assert.AreEqual(inOrderList.Count, preOrderList.Count);
            Assert.AreEqual(inOrderList.Count, postOrderList.Count);

            Assert.AreNotEqual(inOrderList.First(), preOrderList.First());
            Assert.AreNotEqual(preOrderList.First(), postOrderList.First());

            Assert.AreEqual(inOrderList.First(), postOrderList.First());
            Assert.AreEqual(inOrderList.Last(), preOrderList.Last());
            Assert.AreEqual(preOrderList.First(), postOrderList.Last());
        }
    }
}